package ru.susu.algebra.field.quadratic;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

import org.apache.log4j.Logger;

import ru.susu.algebra.util.NumberUtilities;

/**
 * @author akargapolov
 * @since: 28.03.2009
 */
public class QuadraticGeneralUnitExtractor
{
	private static final Logger _log = Logger.getLogger(QuadraticGeneralUnitExtractor.class.getSimpleName());

	private List<BigInteger> _ints = new ArrayList<BigInteger>();
	private List<BigInteger> _divisors = new ArrayList<BigInteger>();
	private List<BigInteger> _subs = new ArrayList<BigInteger>();
	private BigInteger _d;

	public static boolean DO_LOG = true;

	public synchronized QuadraticFieldGeneralForm getGeneralUnit(QuadraticInteger element) throws Exception
	{
		_ints = new ArrayList<BigInteger>();
		_divisors = new ArrayList<BigInteger>();
		_subs = new ArrayList<BigInteger>();
		iterate(element);
		return getCentralUnit();
	}

	private void iterate(QuadraticInteger element) throws Exception
	{
		_d = NumberUtilities.clearSquares(element.getD()).multiply(element.getB()).multiply(element.getB());
		BigInteger sqrt = NumberUtilities.squareRoot(_d);

		//Боревич Шафоревич стр 154
		if (_d.mod(BigInteger.valueOf(4)).equals(BigInteger.ONE))
		{
			_ints.add(sqrt.subtract(BigInteger.ONE).divide(BigInteger.valueOf(2)));
			_divisors.add(BigInteger.valueOf(2));
			_subs.add(BigInteger.ONE.add(_ints.get(0).multiply(BigInteger.valueOf(2))));
		}
		else
		{
			_ints.add(sqrt);
			_divisors.add(BigInteger.ONE);
			_subs.add(sqrt);
		}

		int index = 0;
		BigInteger a, b, c, newInt;
		while (1 == 1)
		{
			a = _subs.get(index);
			b = _divisors.get(index);
			c = _d.subtract(a.multiply(a)); // вычисляем разность квадратов

			if (!c.remainder(b).equals(BigInteger.ZERO))
			{
				throw new Exception("Error in central unit exractor");
			}

			c = c.divide(b); // сокращаем числитель и знаменатель

			if (c.equals(_divisors.get(0)) && a.equals(_subs.get(0)))
			// дробь должна совпадать с начальной, тогда получили период в разложении
			{
				break;
			}

			newInt = a.add(sqrt).divide(c);
			a = a.subtract(c.multiply(newInt));

			_subs.add(a.multiply(BigInteger.valueOf(-1)));
			_divisors.add(c);
			_ints.add(newInt);
			if (DO_LOG)
			{
				System.out.println(_subs.get(_subs.size() - 1) + " " + c + " " + newInt);
			}
			index++;
		}
	}

	private QuadraticFieldGeneralForm getCentralUnit() throws Exception
	{
		int length = _ints.size();
		BigInteger[] a = new BigInteger[length + 2];
		BigInteger[] b = new BigInteger[length + 2];
		b[1] = a[0] = BigInteger.ZERO;
		a[1] = b[0] = BigInteger.ONE;

		for (int i = 0; i < length; i++)
		{
			a[i + 2] = a[i+1].multiply(_ints.get(i)).add(a[i]);
			b[i + 2] = b[i+1].multiply(_ints.get(i)).add(b[i]);
			_log.info("p[" + i + "]=" + a[i+2] + "  q[" + i + "]=" + b[i+2]);
		}
		//выполняем преобразование из A + B (1 + sqrt(bbd))/2 в A + B * (1 - b) / 2 + B * b (1 + sqrt(d)) /2
		BigInteger D = NumberUtilities.clearSquares(_d);	//очищаем _d от квадратов
		BigInteger D1 = NumberUtilities.squareRoot(_d.divide(D));	//узнаем число b
		BigInteger A;
		if (D.remainder(BigInteger.valueOf(4)).equals(BigInteger.ONE))
		{
			A = a[length + 1].add(BigInteger.ONE.subtract(D1).divide(BigInteger.valueOf(2)).multiply(b[length + 1]));	//A = a + (1 - b) / 2 * B
		}
		else
		{
			A = a[length + 1];
		}
		BigInteger B = b[length + 1].multiply(D1);	//B = B * b
		QuadraticFieldGeneralForm result = new QuadraticFieldGeneralForm(A, B, D);
		if (DO_LOG)
		{
			System.out.println(new GeneralUnitFormatter().format(result) + " norm = " + result.norm());
		}
		return result;
	}
}
